//
// Created by EDZ on 2022/2/7.
//

#ifndef INC_2022_1_MONOSTACK_H
#define INC_2022_1_MONOSTACK_H

#include "../head/common.h"

using namespace std;
/**
 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。
 * @param heights
 * @return
 */
//蛮力法
int largestRectangleArea_1(vector<int> &heights) {
    int n = heights.size();
    int m = 0;
    for (int i = 0; i < n; i++) {
        int h = heights[i];
        for (int j = i; j < n; j++) {
            h = min(h, heights[j]);
            m = max(m, (j - i + 1) * h);
        }
    }
    return m;
}

//单调栈
int largestRectangleArea_2(vector<int> &heights) {
    int n = heights.size();
    vector<int> left(n), right(n, n);
    stack<int> mono_stack;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        while (!mono_stack.empty() && heights[mono_stack.top()] >= heights[i]) {
            //*******
            right[mono_stack.top()] = i;
            mono_stack.pop();
        }
        left[i] = mono_stack.empty() ? -1 : mono_stack.top();
        mono_stack.push(i);
    }
    for (int i = 0; i < n; i++) {
        ans = max(ans, (right[i] - left[i] - 1) * heights[i]);
    }
    return ans;
}

/**
 * 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
 * @param matrix
 * @return
 */
int maximalRectangle(vector<vector<char>> &matrix) {
    int m = matrix.size();
    if (m == 0)
        return 0;
    int n = matrix[0].size();
    vector<vector<int>> barArr(m, vector<int>(n, 0));
    for (int j = 0; j < n; j++) {
        for (int i = 0; i < m; i++) {
            if (matrix[i][j] == '1') {
                barArr[i][j] = (i == 0 ? 0 : barArr[i - 1][j]) + 1;
            }
        }
    }

    //将barArr的每行当做柱状图求最大矩形面积
    int res = 0;
    for (int i = 0; i < m; i++) {
        vector<int> left(n), right(n, n);
        stack<int> mono_stack;
        for (int j = 0; j < n; j++) {
            while (!mono_stack.empty() && barArr[i][mono_stack.top()] >= barArr[i][j]) {
                right[mono_stack.top()] = j;
                mono_stack.pop();
            }
            left[j] = mono_stack.empty() ? -1 : mono_stack.top();
            mono_stack.push(j);
        }
        for(int j = 0;j<n;j++){
            res = max(res,(right[j]-left[j]-1)*barArr[i][j]);
        }
    }
    return res;
}

#endif //INC_2022_1_MONOSTACK_H
